package jianzhi_offer;

import java.util.*;

public class _26_字符串的排列 {
    public static void main(String[] args) {
        _26_字符串的排列 test = new _26_字符串的排列();
        Object obj = test.Permutation("aab");
    }

    Set<String> res;
    public ArrayList<String> Permutation(String str) {
        if(str.length() == 0) return new ArrayList<String>();
        this.res = new TreeSet<String>();
        char[] chars = str.toCharArray();
        char[] now = new char[chars.length];
        boolean[] visited = new boolean[chars.length];
        dfs(chars,now,visited,0);
        return new ArrayList<String>(this.res);
    }

    public void dfs(char[] chars,char[] now,boolean[]visited,int index){
        if(index == chars.length) this.res.add(new String(now));
        else{
            for(int i=0;i<chars.length;++i){
                if(!visited[i]){
                    now[index] = chars[i];
                    visited[i] = true;
                    dfs(chars,now,visited,index+1);
                    visited[i] = false;
                }
            }
        }
    }
}
